/* 模块：heap_root
 * 类型：函数单体
 * 功能：用于构成大小根堆
 */

#ifndef xpack_algo_heap_root
#define xpack_algo_heap_root
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::algo_heap_root::inc
#include"dumb/move.hpp"
#include"configure/platform.hpp"
#include"interface/can_compare.hpp"
#include"interface/unified_seq.hpp"
#include"macro/xexport.hpp"
#include"macro/xforward.hpp"
#include"macro/xindex_rollback.hpp"
#include"macro/xmodify.hpp"
#include"macro/xnew.hpp"
#include"macro/xunlikely.hpp"
#include"meta/has_constructor.hpp"
#include"meta/item_origin_of.hpp"
#pragma pop_macro("xuser")

namespace mixc::algo_heap_root{
    #define xheader                                                                 \
    template<                                                                       \
        inc::can_unified_seqlize seq_t,                                             \
        class                    item_t = inc::item_origin_of<seq_t>,               \
        class            forward_item_t = item_t,                                   \
        class                     cmp_t = decltype(inc::default_compare<item_t>)    \
    >                                                                               \
    requires(                                                                       \
        inc::can_compare<cmp_t, item_t> == true                                     \
    )

    // 可以重写
    // 模板类+成员函数
    // template<> inline void change_position<timer_item *>::operator()
    // 静态函数
    // inline void change_position()
    // 这里用模板类代替模板函数，可以在命名空间写错时报错
    // 因为特化有 template<> 存在
    template<class item_t>
    struct change_position{
        void operator()(item_t const &, uxx){
            ;
        }
    };

    /* 函数：大小根堆压栈操作
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - value 为要压栈的元素
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     * 注意：
     * 我们假定 seq [0, length) 区间的元素已经完成了初始化
     * 或者 seq 的元素类似与 int 这样不初始化也可以直接赋值的类型
     * 如果 seq[i] 带有 operator=，并且它没有初始化，那么调用该函数将导致不正确的行为
     */
    xheader inline void push_core(
        seq_t                               seq, 
        uxx                                 seq_length, // 使用此参数，co{0, 0} 不能正确处理
        forward_item_t                   && value, 
        cmp_t                       const & compare
    ){
        // 注意：
        // [value] 可能存在 [seq] 中, 
        // 所以需要一个 [value] 的副本
        item_t insert       = xforward(value);
        uxx    length       = seq_length;
        uxx    i            = length;
        uxx    ii           = 0;
        auto   set          = [&](auto && parent){
            if (i != length){
                seq[i]      = inc::move(parent);
            }
            else{
                xnew(xmodify(seq[i])) item_t(
                    inc::move(parent)
                );
            }

            change_position<item_t>{}(seq[i], i);
        };

        for (; i > 0; i = ii){
            if (auto & parent = seq[ii = (i - 1) >> 1]; compare(parent, insert) <= 0){
                break;
            }
            else{
                set(inc::move(parent));
            }
        }

        set(inc::move(insert));
    }

    /* 函数：大小根堆弹栈操作
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - insert_value 为要插入的元素，通常是当前长度 seq 序列中的最后一个元素
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     * 注意：
     * 我们假定 seq [0, length) 区间的元素已经完成了初始化
     * 或者 seq 的元素类似与 int 这样不初始化也可以直接赋值的类型
     * 如果 seq[i] 带有 operator=，并且它没有初始化，那么调用该函数将导致不正确的行为
     */
    xheader inline item_t pop_core(
        seq_t                               seq, 
        uxx                                 seq_length, // 使用此参数，co{0, 0} 不能正确处理
        uxx                                 index, 
        forward_item_t                   && insert_value, 
        cmp_t                       const & compare
    ){
        // 注意：
        // 提前保存要取出元素的副本，避免后续的元素覆盖它
    #if xis_clang
        volatile // clang14+ bug，它直接忽略了这个返回值，所以需要加上 volatile
    #endif
        item_t  wanted      = inc::move(seq[index]);

        // 下面方式会导致段错误（clang）
        // item_t  wanted      = xvolatile(inc::move(seq[index]));
        item_t  insert      = xforward(insert_value);
        uxx     i           = index;
        uxx     length      = seq_length;
        uxx     left_index  = 1 + (index << 1);

        while(left_index + 1 < length) {
            item_t & left   = seq[left_index];
            item_t & right  = seq[left_index + 1];
            item_t * select;

            // 小根堆 父节点要小于左右节点 所以要找子节点中较小者
            if (compare(left, right) > 0){
                select      = xmodify(right);
                left_index += 1;
            }
            else{
                select      = xmodify(left);
            }

            // 较小的子节点大于等于插入 就不用再下移了
            if (compare(select[0], insert) >= 0){
                break;
            }

            seq[i]          = inc::move(select[0]);
            change_position<item_t>{}(seq[i], i);
            i               = (left_index);
            left_index      = (left_index << 1) + 1;
        }

        // left_index 可能会等于 len，所以这里需要判断一下才能确认是否存在左节点
        if (left_index < length and compare(seq[left_index], insert) < 0){
            seq[i]          = inc::move(seq[left_index]);
            change_position<item_t>{}(seq[i], i);
            i               = left_index;
        }

        seq[i]              = inc::move(insert);
        change_position<item_t>{}(seq[i], i);
        return (item_t &&)wanted; // 消除 clang 编译报错
    }
}

namespace mixc::algo_heap_root::origin{
    using inc::default_compare;
    using inc::default_compare_neg;
}

namespace mixc::algo_heap_root::origin::heap_root{
    /* 函数：大小根堆压栈操作
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - length 为当前 seq 元素个数
     * - value 为要压栈的元素
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     * 注意：
     * 我们假定 seq [0, length) 区间的元素已经完成了初始化
     * 或者 seq 的元素类似与 int 这样不初始化也可以直接赋值的类型
     * 如果 seq[i] 带有 operator=，并且它没有初始化，那么调用该函数将导致不正确的行为
     */

    template<
        inc::can_unified_seqlize seq_t,
        class                    item_t  = inc::item_origin_of<seq_t>,
        class                    cmp_t   = decltype(inc::default_compare<item_t>),
        class                    forward_item_t = item_t
    >
    requires(
        inc::can_compare<cmp_t, item_t> == true
    )
    inline void push(
        seq_t                            && seq,
        uxx                                 length,
        forward_item_t                   && value, 
        cmp_t                       const & compare = inc::default_compare<item_t>
    ){
        inc::unified_seq<seq_t> v{ xforward(seq) };
        push_core(v, length, xforward(value), compare);
    }

    /* 函数：大小根堆弹栈操作
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - length 为 seq 序列的长度
     * - insert_value 为要插入的元素，通常是当前长度 seq 序列中的最后一个元素
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     * 注意：
     * 我们假定 seq [0, length) 区间的元素已经完成了初始化
     * 或者 seq 的元素类似与 int 这样不初始化也可以直接赋值的类型
     * 如果 seq[i] 带有 operator=，并且它没有初始化，那么调用该函数将导致不正确的行为
     */
    template<
        inc::can_unified_seqlize seq_t,
        class                    item_t = inc::item_origin_of<seq_t>,
        class            forward_item_t = item_t,
        class                     cmp_t = decltype(inc::default_compare<item_t>)
    >
    requires(
        inc::can_compare<cmp_t, item_t> == true and 
        inc::has_constructor<item_t, void(forward_item_t &&)>
    )
    inline auto pop(
        seq_t                            && seq, 
        uxx                                 length, 
        forward_item_t                   && insert_value, 
        cmp_t                       const & compare = inc::default_compare<item_t>
    ){
        inc::unified_seq<seq_t> v{ xforward(seq) };
        return pop_core(v, length, 0, xforward(insert_value), compare);
    }

    /* 函数：大小根堆弹栈操作，取出指定索引的元素
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - length 为 seq 序列的长度
     * - index 为要取出元素对应的索引
     * - insert_value 为要插入的元素，通常是当前长度 seq 序列中的最后一个元素
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     * 注意：
     * 我们假定 seq [0, length) 区间的元素已经完成了初始化
     * 或者 seq 的元素类似与 int 这样不初始化也可以直接赋值的类型
     * 如果 seq[i] 带有 operator=，并且它没有初始化，那么调用该函数将导致不正确的行为
     */
    template<
        inc::can_unified_seqlize seq_t,
        class                    item_t = inc::item_origin_of<seq_t>,
        class            forward_item_t = item_t,
        class                    cmp_t  = decltype(inc::default_compare<item_t>)
    >
    requires(
        inc::can_compare<cmp_t, item_t> == true and 
        inc::has_constructor<item_t, void(forward_item_t &&)>
    )
    inline auto pop_by_index(
        seq_t                            && seq, 
        uxx                                 length, 
        ixx                                 index,
        forward_item_t                   && insert_value, 
        cmp_t                       const & compare = inc::default_compare<item_t>
    ){
        xindex_rollback(length, index);

        inc::unified_seq<seq_t> v{ xforward(seq) };

        // 从小根堆的视角，如果 parent 大于 insert_value，那么 insert 数值因该以 push 的方式上游
        if (index != 0 and compare(v[(index - 1) >> 1], insert_value) > 0){
            auto wanted = inc::move(v[index]);
            push_core(v, index, inc::move(insert_value), compare);
            return wanted;
        }
        // 否则只需要以 pop 的方式下沉即可
        else{
            return pop_core(v, length, index, inc::move(insert_value), compare);
        }
    }

    /* 函数：大小根堆弹栈操作
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - length 为 seq 序列的长度
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     * 注意：
     * 我们假定 seq [0, length) 区间的元素已经完成了初始化
     * 或者 seq 的元素类似与 int 这样不初始化也可以直接赋值的类型
     * 如果 seq[i] 带有 operator=，并且它没有初始化，那么调用该函数将导致不正确的行为
     */
    template<
        inc::can_unified_seqlize seq_t,
        class                    item_t = inc::item_origin_of<seq_t>,
        class                     cmp_t = decltype(inc::default_compare<item_t>)
    >
    requires(
        inc::can_compare<cmp_t, item_t> == true
    )
    inline auto pop(
        seq_t                            && seq, 
        uxx                                 length, 
        cmp_t                       const & compare = inc::default_compare<item_t>
    ){
        inc::unified_seq<seq_t> v{ xforward(seq) };
        return pop_core(v, length, 0, inc::move(v[length - 1]), compare);
    }

    /* 函数：大小根堆弹栈操作，取出指定索引的元素
     * 参数：
     * - seq 为满足 can_unified_seqlize 约束的序列类型
     * - length 为 seq 序列的长度
     * - index 为要取出元素对应的索引
     * - compare 为元素比较回调，期望签名如下：
     *      ixx operator()(item_t const & left, item_t const & right)
     *   其中 item_t 是 seq 序列元素的类型，left 和 right 作为 seq 序列中两两比较的元素
     *   当 left 大于 right 返回正数，若小于则返回负数，相等则返回零
     */
    template<
        inc::can_unified_seqlize seq_t,
        class                    item_t = inc::item_origin_of<seq_t>,
        class                     cmp_t = decltype(inc::default_compare<item_t>)
    >
    requires(
        inc::can_compare<cmp_t, item_t> == true
    )
    inline auto pop_by_index(
        seq_t                            && seq, 
        uxx                                 length, 
        ixx                                 index,
        cmp_t                       const & compare = inc::default_compare<item_t>
    ){
        if (length == 1){
            return inc::move(seq[0]);
        }
        return pop_by_index(xforward(seq), length, index, seq[length - 1], compare);
    }

    #undef  xheader
}

#endif

xexport_space(mixc::algo_heap_root::origin)
